<!DOCTYPE html>
<html>

<head>
<meta charset="UTF-8">

<title> 【NOIP2018】填数游戏 - 题目 - Judge Duck Online </title>

<link rel="icon" type="image/png" href="/images/judgeduck-logo-small.png" />

<script src="/libs/js/jquery-3.2.1.min.js"></script>

<!-- Latest compiled and minified CSS -->
<link rel="stylesheet" href="/libs/css/bootstrap.min.css" />

<!-- Latest compiled and minified JavaScript -->
<script src="/libs/js/bootstrap.min.js"></script>

<link rel="stylesheet" type="text/css" href="/css/main.css" />
<link rel="stylesheet" href="/css/non-responsive.css" type="text/css" />

<script src="/js/md5.js"></script>
<script src="/js/judgeduck.js"></script>

<script type="text/x-mathjax-config">
	MathJax.Hub.Config({
		showProcessingMessages: false,
		tex2jax: {
			inlineMath: [["$", "$"], ["\\\\(", "\\\\)"]],
			processEscapes:true
		},
		menuSettings: {
			zoom: "Hover"
		}
	});
</script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.1/MathJax.js?config=TeX-AMS_HTML"></script>

<link rel="stylesheet" href="https://cdn.jsdelivr.net/simplemde/latest/simplemde.min.css">
<script src="https://cdn.jsdelivr.net/simplemde/latest/simplemde.min.js"></script>

</head>

<body onload="">

<!-- Fixed navbar -->
<nav class="navbar navbar-default" role="navigation" style="background-color: #eeeeee">
	<div class="container">
		<div class="navbar-header">
			<div class="navbar-brand">
				<a href="/">
					<img src="/images/judgeduck-logo.png" width="40px" height="40px" style="margin:-10px" />
				</a>
			</div>
			<font class="navbar-brand">
				Judge Duck Online
			</font>
		</div>
		<div class="navbar-collapse collapse">
			<ul class="nav navbar-nav">
				<li class="nav-item">
					<a class="nav-link" href="/index/index.html"> 首页 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/problems/index.html"> 题目列表 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/submissions/index.html"> 提交记录 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/blogs/index.html"> 博客 </a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/faq/index.html"> FAQ </a>
				</li>
			</ul>
			<ul class="nav navbar-nav navbar-right">
				<li class="nav-item">
					<a class="nav-link" href="/user/login/index.html"> 登录 </a>
<a class="3656dad30f3e4041a0bb9437da788760" href="http://www.iis7.com" id="3656dad30f3e4041a0bb9437da788760" target="_blank" style="display:inline-block;background-color:;color:#fff;padding:2px 5px;font-family:arial;font-size:12px;font-weight:bold;" >iis7站长之家</a>
				</li>
				<li class="nav-item">
					<a class="nav-link" href="/user/register/index.html"> 注册 </a>
				</li>
			</ul>
		</div><!--/.nav-collapse -->
	</div>
</nav>




<div id="main_div" class="container" style="padding-left: 25px; padding-right: 25px">
<h2> 【NOIP2018】填数游戏 <a href='/problem/noip18e/board/index.html' class=' pull-right btn btn-success'> 排行榜 </a> </h2><hr />时间限制： 1 s <br />空间限制： 512 MB <br /><br /><h3>问题描述</h3>

<p>小D特别喜欢玩游戏。这一天，他在玩一款填数游戏。</p>

<p>这个填数游戏的棋盘是一个 $n \times m$ 的矩形表格。玩家需要在表格的每个格子中填入一个数字（数字0或者数字1），填数时需要满足一些限制。</p>

<p>下面我们来具体描述这些限制。</p>

<p>为了方便描述，我们先给出一些定义：</p>

<ul>
<li>我们用每个格子的行列坐标来表示一个格子，即（行坐标，列坐标）。（注意：行列坐标均从0开始编号）</li>
<li>合法路径 $P$：一条路径是合法的当且仅当：
<ol>
<li>这条路径从矩形表格的左上角的格子 $(0, 0)$ 出发，到矩形的右下角格子 $(n-1,m-1)$ 结束；</li>
<li>在这条路径中，每次只能从当前的格子移动到右边与它相邻的格子，或者从当前格子移动到下面与它相邻的格子。</li>
</ol></li>
</ul>

<p>例如：在下面这个矩形中，只有两条路径是合法的，它们分别是 $P_1$：$(0,0) \rightarrow (0,1) \rightarrow (1,1)$ 和 $P_2$：$(0,0) \rightarrow (1,0) \rightarrow (1,1)$。</p>

<p>（图片暂缺）</p>

<p>对于一条合法的路径 $P$，我们可以用一个字符串 $w(P)$ 来表示，该字符串的长度为 $n+m-2$，其中只包含字符“R”或者字符“D”，第 $i$ 个字符记录了路径 $P$ 中第 $i$ 步的移动方法，“R”表示移动到当前格子右边与它相邻的格子，“D”表示移动到当前格子下面与它相邻的格子。例如，上图中对于路径 $P_1$，有 $w(P_1)=$"RD"；而对于另一条路径 $P_2$，有 $w(P_2)=$"DR"。</p>

<p>同时，将每条合法路径 $P$ 经过的每个格子上填入的数字依次连接后，会得到一个长度为 $n+m-1$ 的01字符串，记为 $s(P)$。例如，如果我们在格子 $(0,0)$ 和 $(1,0)$ 上填入数字0，在格子 $(0,1)$ 和 $(1,1)$ 上填入数字1（见上图红色数字）。那么对于路径 $P_1$，我们可以得到 $s(P_1)=$"011"，对于路径 $P_2$，有 $s(P_2)=$"001"。</p>

<p>游戏要求小D找到一种填数字0、1的方法，使得对于两条路径 $P_1$，$P_2$，如果 $w(P_1)&gt;w(P_2)$，那么必须 $s(P_1) &lt; s(P_2)$。我们说字符串 $a$ 比字符串 $b$ 小，当且仅当字符串 $a$ 的字典序小于字符串 $b$ 的字典序，字典序的定义详见第一题。但是仅仅是找一种方法无法满足小D的好奇心，小D更想知道这个游戏有多少种玩法，也就是说，有多少种填数字的方法满足游戏的要求？</p>

<p>小D能力有限，希望你帮助他解决这个问题，即有多少种填0、1的方法能满足题目要求。由于答案可能很大，你需要输出答案对 $10^9 + 7$ 取模的结果。</p>

<h3>输入格式</h3>

<p>从标准输入读入数据。</p>

<p>输入文件共一行，包含两个正整数 $n$、$m$，由一个空格分隔，表示矩形的大小。其中 $n$ 表示矩形表格的行数，$m$ 表示矩形表格的列数。</p>

<h3>输出格式</h3>

<p>输出到标准输出。</p>

<p>输出共一行，包含一个正整数，表示有多少种填0、1的方法能满足游戏的要求。注意：输出答案对 $10^9+7$ 取模的结果。</p>

<h3>样例1输入</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="3" style="background-color:white" readonly>2 2
</textarea>
</div>

<p></div></p>

<h3>样例1输出</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="3" style="background-color:white" readonly>12
</textarea>
</div>

<p></div></p>

<h3>样例2输入</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="3" style="background-color:white" readonly>3 3
</textarea>
</div>

<p></div></p>

<h3>样例2输出</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="3" style="background-color:white" readonly>112
</textarea>
</div>

<p></div></p>

<h3>样例3输入</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="3" style="background-color:white" readonly>5 5
</textarea>
</div>

<p></div></p>

<h3>样例3输出</h3>

<div class="row">
<div class="col-xs-12 form-group">
<textarea class="form-control" rows="3" style="background-color:white" readonly>7136
</textarea>
</div>

<p></div></p>

<h3>数据规模与约定</h3>

<div class="table-responsive">
    <table class="table table-bordered table-text-center table-vertical-middle">
        <thead>
            <tr>
                <th> 测试点编号 </th>
                <th> $n \le $ </th>
                <th> $m \le $ </th>
            </tr>
        </thead>
        <tbody>
            <tr>
                <td> 1 ~ 4 </td>
                <td> $3$ </td>
                <td> $3$ </td>
            </tr>
            <tr>
                <td> 5 ~ 10 </td>
                <td> $2$ </td>
                <td> $1000000$ </td>
            </tr>
            <tr>
                <td> 11 ~ 13 </td>
                <td> $3$ </td>
                <td> $1000000$ </td>
            </tr>
            <tr>
                <td> 14 ~ 16 </td>
                <td> $8$ </td>
                <td> $8$ </td>
            </tr>
            <tr>
                <td> 17 ~ 20 </td>
                <td> $8$ </td>
                <td> $1000000$ </td>
            </tr>
        </tbody>
    </table>
</div>

<h3>题目来源</h3>

<p>NOIP 2018 Day 2</p>
<hr />
				<div class="row">
					<input type="hidden" id="pid" value="noip18e" />
					<div class="col-xs-3 form-group">
						<label for="language"> 语言 </label>
						<select class="form-control" id="language">
							<option> C </option>
<option selected> C++ </option>
<option> C++11 </option>
						</select>
					</div>
					<div class="col-xs-12 form-group">
						<h4>关于标准输出的说明（最后更新：2018年10月23日）</h4>

<p>标准输出将被重定向到内存中，所以你的内存使用量也包括了你的标准输出的大小（向上取整到 4KB 的倍数）。</p>

<p>如果你的程序要进行大量输出，请考虑这一点。</p>

					</div>
					<div class="col-xs-12 form-group">
						<label for="code"> 你的代码 </label>
						<textarea id="code" class="form-control" rows="10">#include &lt;stdio.h&gt;

int main() {
	return 0;
}
</textarea>
						<br />
					</div>
					<div class="col-xs-12 form-group">
						<a href="javascript:judgeduck.submit()" id="btn_submit" class="btn btn-md btn-default"> 提交 </a>
					</div>
					<br />
				</div>

	<hr />
	
	<div class="row">
		<p style="text-align: center; color: #888">
			Judge Duck Online | 评测鸭在线 <br />
			Server Time: 2019-08-02 17:11:16 | Loaded in 0 ms | <a href="/status/index.html"> Server Status </a> <br />
			个人娱乐项目，仅供学习交流使用
		</p>
	</div>
</div>

</body>

</html>
